package com.ztom.top100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 找到字符串中所有字母的异位词
 * <p>
 * https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
 *
 * @author ZhangTao
 */
public class Code89FindAnagrams {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0
                || p == null || p.length() == 0
                || s.length() < p.length()) {
            return res;
        }

        int[] sCount = new int[26];
        int[] pCount = new int[26];

        int m = s.length();
        int n = p.length();

        // 统计 p 中字符频次
        for (int i = 0; i < n; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            res.add(0);
        }

        for (int i = 0; i < m - n; i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + n) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                res.add(i + 1);
            }
        }

        return res;
    }
}
